package ZuoShen;

import java.util.HashMap;

public class UnionSet {
    public static HashMap<Integer, Node> indexToNode;
    public Node getNode(int i){
        return indexToNode.get(i);
    }
    public UnionSet(int[] nums) {
        indexToNode = new HashMap<>();
        for(int index : nums){
            Node node = new Node(index);
            node.father = node;
            indexToNode.put(index, node);
        }
    }


    public class Node {
        Node father;
        int size;
        int val;

        public Node(int val) {
            this.val = val;
            this.size = 1;
        }
    }

    public Node findRoot(Node node) {
        Node p1 = node;
        while (p1.father != p1) {
            p1 = p1.father;
        }
        return p1;
    }

    public boolean isSameSet(Node o1, Node o2) {
        Node p1 = findRoot(o1), p2 = findRoot(o2);

        boolean res = (p1 == p2);

//        开始更新father，为了更快
        Node fa1 = p1, fa2 = p2;
        p1 = o1;
        p2 = o2;
        while (p1.father != p1) {
            Node tem = p1.father;
            p1.father = fa1;
            p1 = tem;
        }
        while (p2.father != p2) {
            Node tem = p2.father;
            p2.father = fa2;
            p2 = tem;
        }

        return res;

    }

    public void union(Node o1, Node o2) {
        if (!isSameSet(o1, o2)) {
            Node fa1 = findRoot(o1), fa2 = findRoot(o2);
            if(fa1.size < fa2.size){
                fa1.father = fa2;
                fa2.size = fa1.size + fa2.size;
                fa1.size = 0;
            }else{
                fa2.father = fa1;
                fa1.size = fa1.size + fa2.size;
                fa2.size = 0;
            }
        }
    }
}
